package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/description/
 * @create 2025/9/2 16:09
 * @since JDK17
 */

public class Solution49 {
    static int N = ((int) (1e9 + 7));
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= 1; j--) {
                for (int l = 1; l <= k && l <= j; l++) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - l]) % N;
                }
            }
        }
        return dp[n][target];
    }
}
